GATE PYQ

GATE CSE 2013

Q41.
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

Q42.
Consider the following relational schema.

Q43.
The transport layer protocols used for real time multimedia, file transfer, DNS and email, respectively are

Q44.
Which of the following statements is/are FALSE? 1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. 2. Turing recognizable languages are closed under union and complementation. 3. Turing decidable languages are closed under intersection and complementation. 4. Turing recognizable languages are closed under union and intersection.

Q45.
Which of the following is/are undecidable? 1. G is a CFG. Is L(G) = \Phi? 2. G is a CFG. Is L(G) = \Sigma ^{*} ? 3. M is a Turing machine. Is L(M) regular? 4. A is a DFA and N is an NFA. Is L(A) = L(N)?